import { Compare, defaultCompare, swap } from '../../util';

/**
 * 选择排序(selection-sort)：每轮从数组里选一个比目标项小并且是最小的项（剩余项里最小
 * 的），记住它的下标，在每轮结束时交换目标项与该项的值，所有轮结束后数组就是升序的了。
 * @param array 原数组
 * @param compareFn 比较函数
 * 值得注意的是，在每轮都找出比目标项小的项，这个项还要在剩余项里最小，所以每轮的j都是
 * 从i+1开始的，还要记住最小项的索引。
 * 选择排序与冒泡排序的相同点：都是比较当前项和目标项的大小，并且每轮都让最大或最小项移
 * 到数组的一边。其实就是从剩余项中找出最大或最小项，然后排到数组的一端。
 * 选择排序与冒泡排序的不同点：冒泡排序是一直交换当前项和目标项以达到目的；选择排序是记
 * 住最大或最小项的位置，到一轮快结束时才交换以达到目的。
 * 两者核心思想相似，但处理手段不同，这也决定它们的最差、平均时间复杂度都是O(n\^2)，空间
 * 复杂度都是O(1)。而选择排序的最好时间复杂度还是O(n^2)不能提前退出，因为它减少了交换次数。
 */
export const selectionSort = (array: any[], compareFn = defaultCompare) => {
    // 数组长度
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // 遍历length - 1轮即可，因为最后一轮处理完剩下的就是最大的
    for (let i = 0; i < length - 1; i ++) {
        // 最小项的下标
        let indexMin: number = i;
        // 去遍历除了array[i]的其他项，依次与array[i]比较，得到最小项的下标
        for (let j = i + 1; j < length; j ++) {
            // 比i项的值要小，并且是剩余项里最小的
            if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {
                indexMin = j;
            }
        }
        // 交换当前项与最小项，如果相同就代表剩余项中没有比i小的
        if (i !== indexMin) {
            swap(array, i, indexMin);
        }
    }
    return array;
};
